Syarikat penerbangan itu ditubuhkan sebagai terpisah dari CAAC Xinjiang Regional Authority; [4] ia mula beroperasi pada 1 Januari 1985.[5]

Pada akhir tahun 1993 syarikat penerbangan tersebut mengambil alih lima pesawat siri ATR 72 dengan tempat duduk pertama yang telah ditempah pada bulan Mei di tahun yang sama. Acara ini merupakan tonggak bagi syarikat penerbangan China Xinjiang Airlines kerana menjadi syarikat penerbangan China pertama yang mengambil dan mengoperasikan pesawat ATR.[6] Setakat April 1995 syarikat penerbangan Xinjiang Airlines dimiliki secara merata oleh CAAC dan Wilayah Xinjiang dan ia memiliki armada iaitu sebanyak dua pesawat siri Antonov An-24, sebanyak dua pesawat siri DHC-6 Twin Otters, sebanyak satu pesawat siri Ilyushin Il-86, sebanyak lapan pesawat siri SAP Y-8 dan sebanyak enam pesawat siri Tupolev Tu-154M.[7][nb 1] Setakat April 2000 jawatan presiden disandang oleh Zhang Ruifu, yang menggaji 4.597 pekerja.[9] Pada masa ini, Almaty, Beijing, Changsha, Changzhou, Chengdu, Chongqing, Dalian, Fuzhou, Guangzhou, Guilin, Haikou, Hangzhou, Harbin, Hong Kong, Islamabad, Jinan, Karamay, Korla, Kunming, Lanzhou, Moscow, Novosibirsk, Qingdao, Shanghai, Shenyang, Shenzen, Tashkent, Tianjin, Wuhan, Xian, Xiamen, Xining, Yantai dan Zhengzhou terdiri daripada rangkaian destinasi yang dijadualkan. Pada tahun 2001, pesawat siri Boeing 737-400 dikerahkan di laluan baharu yang menghubungkan Urumqi dengan Hong Kong.[10][11]

Syarikat penerbangan China Southern Airlines (CZ) menyatukan China Northern Airlines dan China Xinjiang Airlines ke dalam operasinya; pengambilalihan tersebut telah diluluskan oleh pihak berkuasa China pada bulan Oktober 2002. [12] Kod IATA ″ XO ″ milik syarikat penerbangan China Xinjiang Airlines diganti dengan CZ untuk operasi domestik pada awal Tahun 2003. [13][14] Setakat Mac 2003, penggantian kod XO dilanjutkan ke semua operasi.[petikan diperlukan]